package Lee_code;

import org.w3c.dom.ls.LSInput;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author blh
 * @date 2024年06月26日 9:34
 */
public class Lee_56_626 {
    static int[][] merge(int[][] intervals) {
        int len = intervals.length;
        // 用来装结果
        List<int[]> list;
        Deque<int[]> deque = new LinkedList<>();
        // 对输入进行排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        list = Arrays.stream(intervals).collect(Collectors.toList());
        // 初始化
        deque.push(list.get(0));
        list.remove(0);

        while (!list.isEmpty()) {
            int nextFirst = list.get(0)[0];
            int nextSecond = list.get(0)[1];
            list.remove(0);
            int curFirst = deque.peek()[0];
            int curSecond = deque.peek()[1];
            if (nextFirst <= curSecond && nextSecond >= curSecond){
                curSecond = nextSecond;
                deque.pop();
                deque.push(new int[]{curFirst, curSecond});
            } else if (nextFirst>curSecond) {
                deque.push(new int[]{nextFirst, nextSecond});
            }
        }
        return null;
    }

    public static void main(String[] args) {
        int[][] input = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        merge(input);
    }
}
